// 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。


// 示例：

// MinStack minStack = new MinStack();
// minStack.push(-2);
// minStack.push(0);
// minStack.push(-3);
// minStack.getMin();   --> 返回 -3.
// minStack.pop();
// minStack.top();      --> 返回 0.
// minStack.getMin();   --> 返回 -2.

#include "stdc++.h"

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        if (m_min >= x) {
            if (!m_stack.empty()) {
                m_stack.push(m_min);
            }
            m_min = x;
        }
        m_stack.push(x);
    }
    
    void pop() {
        if (m_stack.empty()) {
            return;
        }
        if (m_stack.size() == 1) {
            m_min = INT_MAX;
        } else if (m_min == m_stack.top()) {
            m_stack.pop();
            m_min = m_stack.top();
        }
        m_stack.pop();
    }
    
    int top() {
        return m_stack.top();
    }
    
    int getMin() {
        return m_min;
    }
private:
    stack<int> m_stack{};
    int m_min{INT_MAX};
};

/* 单栈
用pair压栈两个数，一个是正常元素，另一个是目前最小值
*/
class MinStack {
public:
    MinStack() {}
    void push(int x) {
        if (m_stack.empty()) {
            m_stack.push(make_pair(x, x));
        } else {
            m_stack.push(make_pair(x, min(x, m_stack.top().second)));
        }
    }
    void pop() {
        m_stack.pop();
    }
    int top() {
        return m_stack.top().first;
    }
    int getMin() {
        return m_stack.top().second;
    }
private:
    stack<pair<int, int>> m_stack{};
};

/* 双栈
一个栈压入正常元素
另一个栈压入最小值
*/
class MinStack {
public:
    MinStack() {}
    void push(int x) {
        m_stack.push(x);
        if (m_stack2.empty()) {
            m_stack2.push(x);
        } else {
            m_stack2.push(min(x, m_stack2.top()));
        }
    }
    void pop() {
        m_stack.pop();
        m_stack2.pop();
    }
    int top() {
        return m_stack.top();
    }
    int getMin() {
        return m_stack2.top();
    }
private:
    stack<int> m_stack{};
    stack<int> m_stack2{};
};